"""
题目：https://leetcode-cn.com/problems/palindrome-linked-list/
    给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
    示例 1：
    输入：head = [1,2,2,1]
    输出：true

思路：遍历链表，把链表中的值存放到一个列表stack中，然后使用双指针判断指针所指位置是否相等，如果存在不相等的情况，则链表不是回文链表，否则是回文链表。
时间复杂度：O(n)
空间复杂度：O(n)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        l,r = 0,len(stack) - 1
        while l <= r:
            if stack[l] != stack[r]:
                return False
            l += 1
            r -= 1
        return True
